package com.zklh.leetcode.top100;

import java.util.*;
import java.util.function.Function;

/**
 * 滑动窗口最大值算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/18
 */
public class Solution239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        Map<Integer, int[]> indexToNode = new HashMap<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            int[] node = new int[]{nums[i],nums[i]};
            maxHeap.add(node);
            indexToNode.put(i, node);
        }
        result[0] = maxHeap.peek()[1];
        for (int i = k; i < nums.length; i++) {
            indexToNode.get(i-k)[1] = Integer.MIN_VALUE;
            int[] node = new int[]{nums[i],nums[i]};
            maxHeap.add(node);
            indexToNode.put(i, node);
            while (maxHeap.peek()[1] == Integer.MIN_VALUE) {
                maxHeap.poll();
            }
            result[i-k+1] = maxHeap.peek()[1];
        }
        return result;
    }

    public static void main(String[] args) {
        Solution239 solution239 = new Solution239();
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(Arrays.toString(solution239.maxSlidingWindow(nums, 3)));
    }
}